package dp.leetcode_198_easy;

public class Rob {
    public int rob1(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[1];
        }
        return dp1(nums, 0);
    }

    //暴力递归
    public int dp1(int[] nums, int start) {
        //base case
        if (start >= nums.length) {
            return 0;
        }
        return Math.max(
                //不偷当前，就选择下一家
                dp1(nums, start + 1),
                //偷当前，选择下下家
                nums[start] + dp1(nums, start + 2)
        );
    }

    //记忆化递归
    public int rob2(int[] nums) {
        //初始化备忘录（傻缓存）
        int[] memory = new int[nums.length];
        //偷到的钱可能为0，所以初始化为-1
        for (int i = 0; i < memory.length; i++) {
            memory[i] = -1;
        }
        return dp2(nums, 0, memory);
    }

    public int dp2(int[] nums, int start, int[] memory) {
        //base case
        if (start >= nums.length) {
            return 0;
        }
        if (memory[start] != -1) {
            return memory[start];
        }
        int res = Math.max(dp2(nums, start + 1, memory), nums[start] + dp2(nums, start + 2, memory));
        memory[start] = res;
        return res;
    }
}
